package com.tgy.leetcode.binarytree;

import javax.xml.soap.Node;
import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-11-03 10:33
 *
 * https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 */
public class _剑指_Offer_34 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        if (Objects.isNull(root)) {

            return null;
        }

        List<List<Integer>> paths = new ArrayList<>();
//        ArrayList<Integer> integers = new ArrayList<>();
//        path(root,integers,sum,paths);

        find(root, sum, paths);
        return paths;
    }

    private void find(TreeNode node, int sum, List<List<Integer>> paths) {

        LinkedList<Integer> integers = new LinkedList<>();

        Stack<TreeNode> stack = new Stack<>();

        TreeNode preNode = null;

        while (true) {

            while (Objects.nonNull(node)) {

                integers.add(node.val);
                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                return;
            }

            node = stack.peek();

            if (Objects.isNull(node.left) && Objects.isNull(node.right)) {

                Integer tmp = 0;
                for (Integer integer : integers) {
                    tmp += integer;
                }

                if (tmp == sum) {

                    paths.add(new LinkedList<>(integers));
                }
            }

            if ((Objects.isNull(node.left) && Objects.isNull(node.right)) ||
                    (preNode != null &&(preNode.equals(node.right) || (node.right == null && preNode.equals(node.left))))) {

                preNode = node;
                stack.pop();
                integers.removeLast();
                node = null;
            }else {

                node = node.right;
            }

        }


    }

    private void path(TreeNode node, List<Integer> integers, int sum,List<List<Integer>> paths) {

        if (Objects.isNull(node)) {

            return;
        }
        integers.add(node.val);
        path(node.left,integers,sum,paths);
        path(node.right,integers,sum,paths);


        if (Objects.isNull(node.left) && Objects.isNull(node.right)) {

            Integer tmp = 0;
            for (Integer integer : integers) {
                tmp += integer;
            }

            if (tmp == sum) {

                paths.add(new ArrayList<>(integers));
            }
        }
        if (!integers.isEmpty()) {

            integers.remove(integers.size()  - 1);
        }
    }
}
